Unrevealing Coin Weighings
In 2007 Alexander Shapovalov suggested a very interesting coin problem. Here is the kindergarten version:
You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.
You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?
To solve this problem, divide the coins into two piles of 50 so that each pile contains exactly one fake coin. Put the piles in the different cups of the scale. The scale will balance, which means that you can’t have the total of exactly one fake coin. Moreover, this proves that each group contains exactly one fake coin. But for any particular coin, the judge won’t have a clue whether it is real or fake.
The puzzle is solved, and though you do not reveal any information about a particular coin, you still give out some information. I would like to introduce the notion of a revealing coefficient. The revealing coefficient is a portion of information you reveal, in addition to proving that there are exactly two fake coins. Before you weighed them all, any two coins out of 100 could have been the two fakes, so the number of equally probable possibilities was 100 choose 2, which is 5050 4950. After you’ve weighed them, it became clear that there was one fake in each pile, so the number of possibilities was reduced to 2500. The revealing coefficient shows the portion by which your possibilities have been reduced. In our case, it is (5050 − 2500)/5050 (4950-2500)/4950, slightly more less than one half.
Now that I’ve explained the kindergarten version, it’s time for you to try the elementary version. This problem is the same as above, except that this time you have 99 coins, instead of 100.
Hopefully you’ve finished that warm-up problem and we can move on to the original Shapovalov’s problem, which was designed for high schoolers.
A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.
You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?
If you are lazy and do not want to solve this problem, but not too lazy to learn Russian, you can find several solutions to this problem in Russian in an essay by Konstantin Knop.
Your challenge is to solve the original Shapovalov puzzle, and for each solution to calculate the revealing coefficient. The best solution will be the one with the smallest revealing coefficient.
Share:
Mary:
Very nice problem! My first attempt at a solution gives a revealing coefficient of about 78%.
Put one genuine coin aside, then divide the remaining coins into three piles of 33, with each pile containing exactly one fake. Two pairwise weighings will demonstrate that three piles are equal in weight, which would not be possible if there were only two fakes. Before the weighing demonstration, there were 100 choose 3 or 161,700 possibilities for the fake coins. Afterwards, the number of possibilities is reduced to 33^3=35,937. So this yields a revealing coefficient of (161,700 – 35,937)/161,700 or a bit less than 78%.
I’m sure there must be more clever ways to do this problem, so I will pose it to the Albany Area Math Circle and see what they can come up with.
I like the notion of a “revealing coefficient.” Reading about it reminded me of learning about Shannon’s approach to measuring information in graduate school with Professor Kenneth Arrow decades ago. I vividly remember thinking that it was very exciting to have such a beautiful and concrete way to measure information as reduction in uncertainty.
But the revealing coefficient is much more intuitive and easy to introduce to younger students than Shannon’s measure.
I have never heard the term “revealing coefficient” used before. When I googled on it, I did not come up with any other examples of its use in an information theory context. But then again, I don’t read Russian. Is “revealing coefficient” a standard term in Russian mathematics? It’s a very nice notion!
12 August 2009, 4:06 pmTanya Khovanova:
Mary,
Your suggestion is not the solution to the problem, because the coin you put aside will be proven to be not fake. Thus, the request not to reveal info about any particular coin doesn’t hold.
12 August 2009, 5:37 pmMary:
Ah, thanks for pointing out that I didn’t read the question carefully enough. I somehow glossed over that point–I had read it too fast and interpreted it as just ruling out specific identification of the fake coins. Back to the drawing board.
12 August 2009, 7:34 pmMary:
Taking the constraint properly into account makes finding even a simple first crack solution somewhat harder and more interesting. My slightly less simple-minded approach (leaving out 4 initially, weighing 3 piles of 32, then swapping the initially set aside 4 and reweighing the new piles of 32 to demonstrate continued equality of weights) yields a revealing coefficient of (161,700 – 32,772)/161,700, which is just under 80%.
But since I’m a bear of very little brain, I’m sure there must be a more clever way to do this that I’m overlooking, so I look forward to seeing someone else post it.
12 August 2009, 8:16 pmTanya Khovanova:
Mary,
If you swap the 4 coins you initially set aside with 4 coins from a particular pile, then those 8 coins that are swapped are real.
12 August 2009, 8:32 pmMary:
Not necessarily. Suppose you initially set aside three fake coins and one real coin. So originally your three piles have all genuine coins. Then you could swap two of the coins (one fake & one real) into pile alpha, one fake into pile beta, and one fake into pile gamma. After the swap, the 3 piles still balance.
Of course, it could also be that you had originally set aside four genuine coins, in which case all 8 coins involved in the swap could be genuine. But it doesn’t have to be, as I’ve illustrated.
Alternatively, if you set aside four genuine coins, you could swap two into pile alpha, one into pile beta, and one into pile gamma, in exchange for one fake & one real from pile alpha, one fake from pile beta, and one fake from pile gamma.
So, the judge has no way to know whether the initial four coins you are swapping in or out are all 4 genuine or 3 fakes plus 1 genuine. Either way, it’s possible to do the swap and maintain 3 even piles.
Basically, my solution allows for the possibility of two equally valid approaches:
Approach 1: The three fakes are initially each planted in piles alpha, beta, and gamma. This leaves 32^3 possibilities in this approach.
Approach 2: The three fakes are initially planted among the four coins set aside. This leaves four possibilities (one for each of the possible identities of the genuine coin among the 4 initially set aside in this approach.)
Since the judge has no way to know which approach you took, there would be 32^3 + 4 = 32,772 possibilities for the identities of the fake coins.
Unless, perhaps, there’s something else I misinterpreted in the problem?
12 August 2009, 9:22 pmTanya Khovanova:
Mary,
My initial impression was that your were swapping all 4 coins together to the same pile. Now I agree with you.
12 August 2009, 10:11 pmSue VanHattum:
I thought this was way cool! I don’t know how trackbacks work, so I just wanted to tell you I put this in the Math Teachers at Play #14, over at Math Mama Writes
20 August 2009, 10:53 pmJBL:
I’m also curious about the answers to one of the questions that Mary asked, namely, did you just invent the notion of “revealing coefficient” on the spot? I agree with her that it seems like an extremely useful idea for introducing some basic ideas of information theory to a not incredibly advanced audience.
Mary, I don’t agree with your computation of the revealing coefficient. If I understand you correctly, the process we follow is this: we have initially three piles of size 32 and a pile of size 4. Let’s name the coins in the pile of size 4 {a, a, b, c}. Then we switch {a, a} for two coins {d, d} from the first of the three big piles, switch {b} for a coin {e} from the second big pile and switch {c} for a coin {f} from the third big pile. Then the following sets of coins could be the counterfeit coins:
* {a, b, c} for one of the a-s (2 ways)
* {d, e, f} for one of the d-s (2 ways)
* a triple of coins, one from each of the big piles, that includes none of a, b, c, d, e, f (30*31*31 = 28830 ways).
This leaves a slightly larger revealing coefficient than you suggested (82.168…%).
An easier-to-explain but less-good solution is to divide the original pile into four piles of size 25 so that there is one counterfeit in three of the piles. Weighing each of those piles against the one “all honest” pile shows that there must be at least 3 counterfeit coins. This gives a revealing coefficient of 1 – 25^3/(100 C 3) = 90.3…%.
25 August 2009, 3:28 pmTanya Khovanova:
JBL,
Yes, I invented the revealing coefficient for this problem.
Also, your solution with 4 piles will not work as the coins in the piles where all of the coins are good would be proven to be all good. Thus, the information about a particular coin is revealed.
25 August 2009, 6:46 pmsandra742:
Hi! I was surfing and found your blog post… nice! I love your blog. 🙂 Cheers! Sandra. R.
9 September 2009, 9:30 amDaran:
sandra742 fails the Turing test. I suspect it is spam.
I was initially puzzled by this, as 100 choose 2 is 4950. I then realized that what you meant was 100 choose 1 or 2, which is 5050.
For the elementary version of the puzzle, two facts are apparent.
1. Every weighing must set aside an odd number of coins, not one.
2. Every weighing must balance (otherwise the heavy side would be revealed to contain only genuine coins).
The task then is to exhibit a sequence of weighings, all of which balance, but which, if there had been only a single fake coin, some would not have balanced.
Setting three coins aside, weigh 48 coins against 48 to show that they balance.
Swap the three coins for two from one of the pans and one from the other, and show that they balance.
Before you weighed them all, one or two coins out of 99 could have been fake, so the number of equally probable possibilities was 99 choose 1 or 2, which is 4950.
After weighing, one fake could be among the 46 coins never swapped in the first pan, and the other in the 47 never swapped in the other, for a total of 2162 possibilities. Or they could be among the three swapped out, or the three swapped in, for an additional 4 possiblities. The revealing coefficient is then (4950 – 2166) / 4950 = 0.562.
This is the best we can do. If, for example, we instead set aside 5 coins, and swap 3 and 2 to the two pans respectively then after weighing the number of possibilities would be 45 * 46 + 3 * 2 + 3 * 2 = 2082
Turning to the original Shapovalov problem, I note that fact 1 above is replaced by a requirement that it is always an even number of coins set aside (including none). Also the requirement that the pans always balance no longer applies. Mary’s solution, which is analogous to the one given above, is probably the best with all weighings balancing. It is not clear to me that solutions with non-redundant non-balancing weighings can’t exist, but despite considerable brain-wracking, I can’t find one.
12 September 2009, 8:10 amTanya Khovanova:
Daran.
Thank you for pointing out my arithmetic mistake. And sorry that it confused you. I corrected it. I wanted the revealing coefficient to compare what you are supposed to prove with the info you actually reveal.
Also, I wonder what do you mean by “sandra failing the Turing test”? My spam catcher allowed her to pass.
12 September 2009, 9:19 amDaran:
Some blogs are configured so that the first comment by an individual commenter goes into moderation. Once manually approved, subsequent comments are approved automatically.
Faced with that configuration, spammers sometimes post innocuous-looking comments without a spammy link in the hope that they will be approved, allowing the real spammy payload to be sent later.
No spam catcher is perfect, and this kind is more difficult to recognize automatically than the usual. What marks them out to human eyes is that they are completely generic. The comment could just as well have been posted to any other blog. There is nothing in it specific to your blog that would indicate a real person had read it and wanted to comment on it. The other big giveaway is that Sandra’s link doesn’t point to anything.
Sandra could prove me wrong by replying to this comment.
12 September 2009, 10:07 amHemant Agarwal:
You say that “Moreover, this proves that each group contains exactly one fake coin”…this is not true..this only shows that the total number of fake coins is even and that the fake coins are equally distributed between the 2 pans..it doesn’t prove that there are exactly 2 fake coins
27 July 2012, 1:08 pmHemant Agarwal:
ohhh…sorry..i didn’t read that the initial statement that “You present 100 identical coins to a judge, who knows that among them are either one or two fake coins”
27 July 2012, 1:11 pm